package algo.A05_其他排序算法;

import util.ArrayUtil;

public class M03_堆排序_大顶堆 {
    public static void main(String[] args) {
        int[] arr = ArrayUtil.getRandomArr(10, 0, 30);
        ArrayUtil.print(arr);
        heapSort(arr);
        ArrayUtil.print(arr);
    }

    /**
     * 堆排序入口
     * @param arr
     */
    private static void heapSort(int[] arr) {
        build_maxHeap(arr);
        for (int i = arr.length - 1; i > 0 ; i--) {
            ArrayUtil.swap(arr,i,0);
            heapify(arr,0,i);
        }
    }

    /**
     * 构建大顶堆
     * @param arr
     */
    private static void build_maxHeap(int[] arr) {
        //从最后一个结点的父结点开始heapify
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
    }

    /**
     * 维护堆的性质(大顶堆)
     * @param arr
     * @param root
     * @param length
     */
    private static void heapify(int[] arr, int root, int length) {
        int max_index = root;//假设根节点就是最大的
        int lChild = root * 2 + 1;
        int rChild = root * 2 + 2;
        if (lChild < length && arr[lChild] > arr[max_index]) {
            max_index = lChild;
        }
        if (rChild < length && arr[rChild] > arr[max_index]) {
            max_index = rChild;
        }
        if (max_index != root) {
            ArrayUtil.swap(arr, max_index, root);
            heapify(arr, max_index, length);
        }
    }
}
